题目分析

看到成对的括号问题，脑中就会自然想到括号匹配，顺理成章的想到栈的思路。这个题目是否可以从这里入手呢？前一段时间没有经常写博客，因为忙于毕业论文和答辩的事情，搞得人焦头烂额，现在很多事情已经解决，可以继续和朋友们分享博客了。因为想学习一下Android，毕竟在国内企业发展，了解一些Android毕竟不是坏事，而偏偏Google现在首推Kotlin语言进行Android开发，因此这段时间也顺带学习了一下Kotlin，有时间也会给小伙伴们科普Kotlin语言的学习。以后当作练手，在博客的题解中，从C++，Java，Python和Kotlin中随机选择2个给出答案。因为之前Python和C++练习的比较多，因此权重稍微少一些，控制在比例分别控制在0.17，0.33，0.17，0.33。希望小伙伴们也要学习我的这个方法，对新语言多多练习，对已经会使用的语言也不能放弃。

栈

这里就介绍栈的方法，以(u(love)i)为例，依次将元素入栈，如果出现了右括号，则将对应左括号之间的所有字符反转，并入栈。在本例中，e后面出现第一次右括号，对应的左括号在l之前，因此将两者之间的love反转，变为evol，然后入栈，此时栈中元素为uevol，然后i入栈，又遇到右括号，此时对应的左括号在u之前，因此将两者之间的uevoli反转，变为iloveu，然后再入栈。此时没有元素，此时顺序读出即可。但是要注意，这个题目要求将反转的结果输出，因此栈无法顺序读出，因此可以使用双端队列代替栈。
算法的**时间复杂度为$O(n^2)$，空间复杂度为$O(n)$**。
如下使用C++语言求解

class Solution {
public:
    string reverseParentheses(string s) {
        deque<int> q;
        for (char c : s) {
            if (c != ')') q.push_back(c);
            else {
                string cur = "";
                while (q.back() != '(') {
                    cur += q.back();
                    q.pop_back();
                }
                q.pop_back();
                for (char cc : cur) q.push_back(cc);
            }
        }
        string res = "";
        for (char c : q) res += c;
        return res;
    }
};

如下使用Java语言求解

class Solution {
    public String reverseParentheses(String s) {
        LinkedList<Character> arr = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            if (cur != ')') arr.addLast(cur);
            else {
                StringBuilder pop = new StringBuilder();
                while (arr.getLast() != '(') {
                    pop.append(arr.removeLast());
                }
                arr.removeLast();
                for (int j = 0; j < pop.length(); j++) {
                    arr.addLast(pop.charAt(j));
                }
            }
        }
        StringBuilder res = new StringBuilder();
        while (!arr.isEmpty()) { res.append(arr.removeFirst()); }
        return res.toString();
    }
}

刷题总结

有小伙伴们说这个题目是华为的笔试题，这太正常了，相比于字节和阿里的变态笔试题，华为的笔试题相对轻松一些，一般是中等难度的题目。而且括号问题是笔试面试的经典题型之一，一定要牢牢掌握。